<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 补种未成活胡杨（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h3 id="main-toc">题目描述</h3> 
<p>近些年来&#xff0c;我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨&#xff08;编号1-N&#xff09;&#xff0c;排成一排。</p> 
<p>一个月后&#xff0c;有M棵胡杨未能成活。</p> 
<p>现可补种胡杨K棵&#xff0c;请问如何补种&#xff08;只能补种&#xff0c;不能新种&#xff09;&#xff0c;可以得到最多的连续胡杨树&#xff1f;</p> 
<p></p> 
<h3 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h3> 
<p>N 总种植数量&#xff0c;1 &lt;&#61; N &lt;&#61; 100000</p> 
<p>M 未成活胡杨数量&#xff0c;M 个空格分隔的数&#xff0c;按编号从小到大排列&#xff0c;1 &lt;&#61; M &lt;&#61; N</p> 
<p>K 最多可以补种的数量&#xff0c;0 &lt;&#61; K &lt;&#61; M</p> 
<p></p> 
<h3 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h3> 
<p>最多的连续胡杨棵树</p> 
<p></p> 
<h3 id="%E7%94%A8%E4%BE%8B">用例</h3> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td>输入</td><td> <p>5<br /> 2<br /> 2 4<br /> 1</p> </td></tr><tr><td>输出</td><td> <p>3</p> </td></tr><tr><td>说明</td><td>补种到2或4结果一样&#xff0c;最多的连续胡杨棵树都是3。</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:58px;">输入</td><td style="width:440px;">10<br /> 3<br /> 2 4 7<br /> 1</td></tr><tr><td style="width:58px;">输出</td><td style="width:440px;">6</td></tr><tr><td style="width:58px;">说明</td><td style="width:440px;">补种第7棵树&#xff0c;最多连续胡杨树棵数位6&#xff08;5&#xff0c;6&#xff0c;7&#xff0c;8&#xff0c;9&#xff0c;10&#xff09;</td></tr></tbody></table> 
<p> </p> 
<h3 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">双指针解法</h3> 
<p>这题感觉还是比较难的&#xff0c;按照用例意思&#xff0c;种了5棵树&#xff0c;我们用1代表活树&#xff0c;则&#xff1a;</p> 
<p>1&#xff0c;1&#xff0c;1&#xff0c;1&#xff0c;1</p> 
<p>然后死了2两棵树&#xff0c;分别是第2棵树、第4棵树&#xff0c;我们用0代表死树&#xff0c;则&#xff1a;</p> 
<p>1&#xff0c;0&#xff0c;1&#xff0c;0&#xff0c;1</p> 
<p>现在我们可以在死树位置&#xff0c;补种一颗活树&#xff0c;即可以将某个0替换为1&#xff0c;问&#xff0c;此时连续活树的最大长度&#xff1f;</p> 
<p>转换一下问题&#xff0c;其实就是&#xff1a;</p> 
<p>在1,0,1,0,1数列中&#xff0c;求包含一个0的最长子序列?</p> 
<p>这其实是一个典型的滑动窗口问题&#xff0c;而滑动窗口的实现依赖于双指针&#xff0c;即两个指针之间的序列就是滑动窗口&#xff0c;我们只要保证滑动窗口内部只含1个0即可</p> 
<p><img alt="" height="760" src="https://img-blog.csdnimg.cn/d3d850a5c4974368a1d0a13b60a0d21a.png" width="1200" /></p> 
<p>我们在举一个例子&#xff0c;数列&#xff1a;1&#xff0c;0&#xff0c;0&#xff0c;0&#xff0c;1&#xff0c;可以补种2棵树</p> 
<p><img alt="" height="740" src="https://img-blog.csdnimg.cn/d0fb9afe2bf14d91965525d6e1e6878c.png" width="771" /></p> 
<p>我们可以通过这两个例子发现&#xff0c;比较难的实现是left指针的移动&#xff0c;我们需要记录right指针每次扫描到0的索引&#xff0c;当滑动窗口内0超过制定数量时&#xff0c;我们可以抛弃记录的滑动窗口内部的第一个0及之前部分&#xff0c;因此即让left指针移动到记录的第一个0的右边。</p> 
<p></p> 
<p>下面源码实现中&#xff0c;我使用的occur来记录滑动窗口中0出现的索引位置&#xff0c;当0超标时&#xff0c;就occur.shift()弹出第一个0的索引位置index&#xff0c;然后让left &#61; index &#43; 1&#xff0c;即能起到帮助滑动窗口去除1个0的效果。</p> 
<p>下面源码中&#xff0c;还有一个地方的实现可能会让大家产生疑问&#xff0c;那就是maxLen&#xff0c;即最长子序列长度的计算&#xff0c;我用了两种公式&#xff1a;</p> 
<ol><li>maxLen &#61; Math.max(maxLen, right - left);</li><li>maxLen &#61; Math.max(maxLen, right - left &#43; 1);</li></ol> 
<p>第一个公式是当0超标时&#xff0c;最长子序列的长度计算&#xff0c;如下图</p> 
<p><img alt="" height="124" src="https://img-blog.csdnimg.cn/7f98cfb662664999990dd40fef5b5744.png" width="299" /></p> 
<p> right &#61; 3&#xff0c;left&#61;0&#xff0c;此时滑动窗口长度为 right - left</p> 
<p>第二个公式是0不超标时&#xff0c;最长子序列的长度计算&#xff0c;如下图</p> 
<p><img alt="" height="118" src="https://img-blog.csdnimg.cn/faf98f0c1cf542c1b28b201c82c8ddbe.png" width="250" /></p> 
<p>right &#61; 2, left &#61; 0&#xff0c;此时滑动窗口长度为 right - left &#43; 1</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 4) {
    let n &#61; lines[0] - 0;
    let m &#61; lines[1] - 0;
    let k &#61; lines[3] - 0;

    const arr &#61; new Array(n).fill(1);

    let idx &#61; lines[2].split(&#34; &#34;).slice(0, m);
    for (let i &#61; 0; i &lt; idx.length; i&#43;&#43;) {
      arr[idx[i] - 1] &#61; 0;
    }

    console.log(slide(arr, k));

    lines.length &#61; 0;
  }
});

/* 滑动窗口 */
function slide(arr, k) {
  let left &#61; 0;
  let occur &#61; [];
  let maxLen &#61; 0;
  for (let right &#61; 0; right &lt; arr.length; right&#43;&#43;) {
    if (arr[right] &#61;&#61;&#61; 0) {
      occur.push(right);

      if (occur.length &gt; k) {
        maxLen &#61; Math.max(maxLen, right - left);
        left &#61; occur.shift() &#43; 1;
        continue;
      }
    }
    maxLen &#61; Math.max(maxLen, right - left &#43; 1);
  }
  return maxLen;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();
    int m &#61; sc.nextInt();

    int[] arr &#61; new int[n];
    Arrays.fill(arr, 1);

    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      int deadIdx &#61; sc.nextInt() - 1;
      arr[deadIdx] &#61; 0;
    }

    int k &#61; sc.nextInt();

    System.out.println(getResult(arr, k));
  }

  public static int getResult(int[] arr, int k) {
    int left &#61; 0;
    LinkedList&lt;Integer&gt; occur &#61; new LinkedList&lt;&gt;();
    int maxLen &#61; 0;

    for (int right &#61; 0; right &lt; arr.length; right&#43;&#43;) {
      if (arr[right] &#61;&#61; 0) {
        occur.addLast(right);

        if (occur.size() &gt; k) {
          maxLen &#61; Math.max(maxLen, right - left);
          left &#61; occur.removeFirst() &#43; 1;
          continue;
        }
      }
      maxLen &#61; Math.max(maxLen, right - left &#43; 1);
    }
    return maxLen;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())
m &#61; int(input())

deadIdx &#61; list(map(int, input().split()))
arr &#61; [1]*n
for i in range(m):
    arr[deadIdx[i]-1] &#61; 0

k &#61; int(input())


# 算法入口
def getResult(arr, n, m, k):
    left &#61; 0
    occur &#61; []
    maxLen &#61; 0

    for right in range(n):
        if arr[right] &#61;&#61; 0:
            occur.append(right)

            if len(occur) &gt; k:
                maxLen &#61; max(maxLen, right - left)
                left &#61; occur.pop(0) &#43; 1
                continue

        maxLen &#61; max(maxLen, right - left &#43; 1)

    return maxLen


# 算法调用
print(getResult(arr, n, m, k))
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;

#define MAX(a,b) (a) &gt; (b) ? (a) : (b)

typedef struct ListNode {
    int ele;
    struct ListNode* next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode* head;
    ListNode* tail;
} LinkedList;

LinkedList* new_LinkedList();
void addLast_LinkedList(LinkedList* link, int ele);
int removeFirst_LinkedList(LinkedList* link);

int getResult(int n, int arr[], int k);

int main() {
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    int m;
    scanf(&#34;%d&#34;, &amp;m);

    int arr[n];
    for(int i&#61;0; i&lt;n; i&#43;&#43;) {
        arr[i] &#61; 1;
    }

    for(int i&#61;0; i&lt;m; i&#43;&#43;) {
        int deadIdx;
        scanf(&#34;%d&#34;, &amp;deadIdx);

        arr[deadIdx - 1] &#61; 0;
    }

    int k;
    scanf(&#34;%d&#34;, &amp;k);

    printf(&#34;%d\n&#34;, getResult(n, arr, k));

    return 0;
}

int getResult(int n, int arr[], int k) {
    int left &#61; 0;
    LinkedList* occur &#61; new_LinkedList();
    int maxLen &#61; 0;

    for(int right &#61; 0; right &lt; n; right&#43;&#43;) {

        if(arr[right] &#61;&#61; 0) {
            addLast_LinkedList(occur, right);

            if(occur-&gt;size &gt; k) {
                maxLen &#61; MAX(maxLen, right - left);
                left &#61; removeFirst_LinkedList(occur) &#43; 1;
                continue;
            }
        }

        maxLen &#61; MAX(maxLen, right - left &#43; 1);
    }

    return maxLen;
}

LinkedList* new_LinkedList() {
    LinkedList* link &#61; (LinkedList*) malloc(sizeof(LinkedList));
    link-&gt;head &#61; NULL;
    link-&gt;tail &#61; NULL;
    link-&gt;size &#61; 0;

    return link;
}

void addLast_LinkedList(LinkedList* link, int ele) {
    ListNode* node &#61; (ListNode*) malloc(sizeof(ListNode));

    node-&gt;ele &#61; ele;
    node-&gt;next &#61; NULL;


    if(link-&gt;size &#61;&#61; 0) {
        link-&gt;head &#61; node;
        link-&gt;tail &#61; node;
    } else {
        link-&gt;tail-&gt;next &#61; node;
        link-&gt;tail &#61; node;
    }

    link-&gt;size&#43;&#43;;
}

int removeFirst_LinkedList(LinkedList* link) {
    if(link-&gt;size &#61;&#61; 0) exit(-1);

    ListNode* removed &#61; link-&gt;head;

    if(link-&gt;size &#61;&#61; 1) {
        link-&gt;head &#61; NULL;
        link-&gt;tail &#61; NULL;
    } else {
        link-&gt;head &#61; link-&gt;head-&gt;next;
    }

    link-&gt;size--;

    int res &#61; removed-&gt;ele;
    free(removed);

    return res;
}</code></pre> 
<p></p> 
<h3 id="%E5%8D%95%E6%8C%87%E9%92%88%E5%AE%9E%E7%8E%B0%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3">单指针解法</h3> 
<p>前面的算法是基于双指针实现的滑动窗口&#xff0c;并且为了记录left指针的位置&#xff0c;还额外创建了一个occur数组来保存right指针扫描过程中遇到的0&#xff0c;但是实际输入的第三行就提供了死树的索引位置&#xff0c;如本题用例中的第三行输入的2 4&#xff0c;因此我们的occur数组算是一个冗余。</p> 
<p>我们基于死树索引位置&#xff0c;以及补种k值&#xff0c;就可以得出left、right指针位置&#xff0c;即找出滑动窗口&#xff0c;逻辑如下&#xff1a;</p> 
<p>我们用一个指针来从左到右遍历每一棵死树&#xff0c;死树用红色标记&#xff0c;如下图第一行</p> 
<p>如果k&#61;1的话&#xff0c;则滑动窗口只能包含遍历到的死树&#xff0c;不能包含其他死树&#xff0c;因此滑动窗口有如下三种情况</p> 
<p><img alt="" height="719" src="https://img-blog.csdnimg.cn/ca3c4cb1508141fb8c8411080f7fc4c7.png" width="719" /></p> 
<p>如果k&#61;2&#xff0c;则情况如下</p> 
<p><img alt="" height="538" src="https://img-blog.csdnimg.cn/99c30ce3eac94eefb9ff9142d15f0299.png" width="586" /></p> 
<p>因此我们可以得出结论&#xff1a;</p> 
<p>假设总树有n棵&#xff0c;死树有m棵&#xff0c;且死树索引保存在arr中&#xff0c;比如arr &#61; [2,5,8]&#xff0c;补种k棵。</p> 
<p>则此时指向死树的单指针的移动范围在arr数组的 0 ~ m-k ,</p> 
<p>而滑动窗口的范围在&#xff1a;</p> 
<p>如果滑动窗口包含边界的话&#xff0c;即包含总树的开头或结尾&#xff0c;此时单指针的指向固定为&#xff1a;</p> 
<ul><li>arr[0]&#xff08;包含开头&#xff09;&#xff0c;此时滑动窗口的长度为 arr[0&#43;k] - 1&#xff0c;如下图所示</li></ul> 
<p><img alt="" height="203" src="https://img-blog.csdnimg.cn/3f0035d681c64062b20e8d7175d950d1.png" width="500" /></p> 
<ul><li>arr[m-k]&#xff08;包含结尾&#xff09;&#xff0c;此时滑动窗口的长度为 n - arr[m-k-1] &#xff0c;如下图所示</li></ul> 
<p> <img alt="" height="183" src="https://img-blog.csdnimg.cn/fd633dcb0e1148bdb178fdfeb41e3888.png" width="489" /></p> 
<p> 如果滑动窗口的范围不包含总树边界&#xff0c;即在中间位置&#xff0c;则滑动窗口的长度为 arr[i&#43;k] - arr[i-1] - 1&#xff0c;如下图所示</p> 
<p><img alt="" height="187" src="https://img-blog.csdnimg.cn/03725003d76e405280c4276edeec6da1.png" width="475" /></p> 
<p></p> 
<hr /> 
<p>2023.09.09</p> 
<p>上面逻辑应该考虑下m &#61;&#61; k的情况&#xff0c;即补种数 &#61;&#61; 未成活数&#xff0c;此时可以直接返回n&#xff0c;即补种后所有树都成活了。</p> 
<p></p> 
<h4 style="background-color:transparent;">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 4) {
    let n &#61; lines[0] - 0; // 一共多少颗树
    let m &#61; lines[1] - 0; // 死了多少棵树
    let idx &#61; lines[2]
      .split(&#34; &#34;)
      .slice(0, m)
      .map((ele) &#61;&gt; parseInt(ele)); // 死树的序号&#xff0c;从1开始
    let k &#61; lines[3] - 0; // 补种多少颗树

    console.log(slide(n, m, idx, k));

    lines.length &#61; 0;
  }
});

/**
 * 滑动窗口
 * &#64;param {number} n 总共多少棵树
 * &#64;param {number} m 总共死了多少棵树
 * &#64;param {Array} idx 死树序号&#xff0c;从1开始
 * &#64;param {number} k 补种多少棵树
 * &#64;return {number} 连续最长活树的长度
 */
function slide(n, m, idx, k) {
  if (m &#61;&#61; k) {
    return n;
  }

  let maxLen &#61; 0;
  for (let i &#61; 0; i &lt;&#61; m - k; i&#43;&#43;) {
    if (i &#61;&#61;&#61; 0) {
      maxLen &#61; Math.max(maxLen, idx[i &#43; k] - 1);
    } else if (i &#61;&#61;&#61; m - k) {
      maxLen &#61; Math.max(maxLen, n - idx[i - 1]);
    } else {
      maxLen &#61; Math.max(maxLen, idx[i &#43; k] - idx[i - 1] - 1);
    }
  }

  return maxLen;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();
    int m &#61; sc.nextInt();

    int[] deadIdx &#61; new int[m];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      deadIdx[i] &#61; sc.nextInt();
    }

    int k &#61; sc.nextInt();

    System.out.println(getResult(n, m, deadIdx, k));
  }

  /**
   * &#64;param n 总共多少棵树
   * &#64;param m 总共死了多少棵树
   * &#64;param deadIdx 数组&#xff0c;元素是死树序号&#xff0c;从1开始
   * &#64;param k 补种多少棵树
   * &#64;return 连续最长活树的长度
   */
  public static int getResult(int n, int m, int[] deadIdx, int k) {
    if (m &#61;&#61; k) return n;

    int maxLen &#61; 0;

    for (int i &#61; 0; i &lt;&#61; m - k; i&#43;&#43;) {
      if (i &#61;&#61; 0) {
        maxLen &#61; Math.max(maxLen, deadIdx[i &#43; k] - 1);
      } else if (i &#61;&#61; m - k) {
        maxLen &#61; Math.max(maxLen, n - deadIdx[i - 1]);
      } else {
        maxLen &#61; Math.max(maxLen, deadIdx[i &#43; k] - deadIdx[i - 1] - 1);
      }
    }
    return maxLen;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())
m &#61; int(input())
deadIdx &#61; list(map(int, input().split()))
k &#61; int(input())


# 算法入口
def getResult(n, m, deadIdx, k):
    if m &#61;&#61; k:
        return n

    maxLen &#61; 0

    for i in range(m - k &#43; 1):
        if i &#61;&#61; 0:
            maxLen &#61; max(maxLen, deadIdx[i &#43; k] - 1)
        elif i &#61;&#61; m - k:
            maxLen &#61; max(maxLen, n - deadIdx[i - 1])
        else:
            maxLen &#61; max(maxLen, deadIdx[i &#43; k] - deadIdx[i - 1] - 1)

    return maxLen

# 算法调用
print(getResult(n, m, deadIdx, k))</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;

#define MAX(a,b) (a) &gt; (b) ? (a) : (b)

int getResult(int n, int m, int deadIdx[], int k);

int main() {
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    int m;
    scanf(&#34;%d&#34;, &amp;m);

    int deadIdx[m];
    for(int i&#61;0; i&lt;m; i&#43;&#43;) {
        scanf(&#34;%d&#34;, &amp;deadIdx[i]);
    }

    int k;
    scanf(&#34;%d&#34;, &amp;k);

    printf(&#34;%d\n&#34;, getResult(n, m, deadIdx, k));

    return 0;
}

int getResult(int n, int m, int deadIdx[], int k) {
    if(m &#61;&#61; k) return n;

    int maxLen &#61; 0;

    for(int i&#61;0; i&lt;&#61;m-k; i&#43;&#43;) {
        if(i &#61;&#61; 0) {
            maxLen &#61; MAX(maxLen, deadIdx[i&#43;k] - 1);
        } else if(i &#61;&#61; m - k) {
            maxLen &#61; MAX(maxLen, n - deadIdx[i-1]);
        } else {
            maxLen &#61; MAX(maxLen, deadIdx[i&#43;k] - deadIdx[i-1] - 1);
        }
    }

    return maxLen;
}</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>